package com.zjsru.plan2024.oneday;

import java.util.Stack;

/**
 * 2434. 使用机器人打印字典序最小的字符串
 *
 * @Author: cookLee
 * @Date: 2025-06-06
 */
public class RobotWithString {

    /**
     * 主
     * \
     * 删除字符串 s 的 第一个 字符，并将该字符给机器人。机器人把这个字符添加到 t 的尾部。
     * 删除字符串 t 的 最后一个 字符，并将该字符给机器人。机器人将该字符写到纸上。
     * \
     * 输入：s = "zza"
     * 输出："azz"
     * 解释：用 p 表示写出来的字符串。
     * 一开始，p="" ，s="zza" ，t="" 。
     * 执行第一个操作三次，得到 p="" ，s="" ，t="zza" 。
     * 执行第二个操作三次，得到 p="azz" ，s="" ，t="" 。
     * \
     * 输入：s = "bac"
     * 输出："abc"
     * 解释：用 p 表示写出来的字符串。
     * 执行第一个操作两次，得到 p="" ，s="c" ，t="ba" 。
     * 执行第二个操作两次，得到 p="ab" ，s="c" ，t="" 。
     * 执行第一个操作，得到 p="ab" ，s="" ，t="c" 。
     * 执行第二个操作，得到 p="abc" ，s="" ，t="" 。
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        RobotWithString robotWithString = new RobotWithString();
        System.out.println(robotWithString.robotWithString("bac"));
    }

    public String robotWithString(String s) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }
        StringBuilder sb = new StringBuilder();
        Stack<Character> stack = new Stack<>();
        char minChar = 'a';
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            //更新对应字符的剩余计数
            stack.push(c);
            count[c - 'a']--;
            //当前字符 minChar 如果没有剩余，则向后寻找下一个可用字符。
            //直到找到还有剩余的字符或达到 'z'。
            while (minChar != 'z' && count[minChar - 'a'] == 0) {
                minChar++;
            }
            while (!stack.isEmpty() && stack.peek() <= minChar) {
                sb.append(stack.pop());
            }
        }
        return sb.toString();
    }

}
